﻿//----------------------------------------------------------------
// Copyright (c) 2011-2013 
// All rights reserved.
// Author: Ben DaoWei 
// Contact: bendaowei@gmail.com
// Web Link: http://xnaeditor.codeplex.com
// ----------------------------------------------------------------

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace UnityEngine.Terrain
{
    // used for A* Search algorithm
    public class HValue
    {
        public HValue()
        {
            this.Key = 0.0f;
        }

        /// <summary>
        ///  0 means not in the queue, 1 in the queue, 2 has dequene 
        /// </summary>
        public int Mark;
        public float Key;
        public HValue Previous;
        public float Cost;
        public int X;
        public int Y;
        public int Depth;

        public void Set(int x, int y, float cost, float key)
        {
            this.X = x;
            this.Y = y;
            this.Cost = cost;
            this.Key = key;
        }

        public void Reset()
        {
            Key = 10000000;
            this.Mark = -1;
            Previous = null;
            Cost = 10000000;
            X = 0;
            Y = 0;
            Depth = 0;
        }

        public static bool Compare(HValue left, HValue right)
        {
            if (Math.Abs(right.Key - left.Key) < 0.1f)
            {
                if (Math.Abs(right.Cost - left.Cost) < 0.1f)
                    return false;
                else
                    return left.Cost > right.Cost;
            }
            else
                return left.Key < right.Key;
        }
    }

    public class Heap
    {
        public List<HValue> _Values = new List<HValue>();

        public int Count
        {
            get
            {
                if (_Values == null)
                    return 0;
                return _Values.Count;
            }
        }

        public int PushCount
        {
            set;
            get;
        }

        public bool IsEmpty
        {
            get
            {
                return _Values == null || _Values.Count == 0;
            }
        }

        public Heap()
        {
            this.Reset();
        }

        public void Clear()
        {
            this.Reset();
        }

        public int Find(HValue instance)
        {
            if (_Values != null)
            {
                for (int i = 0; i < _Values.Count; i++)
                {
                    if (instance.X == _Values[i].X &&
                        instance.Y == _Values[i].Y)
                        return i;
                }
            }
            return -1;
        }

        private void Reset()
        {
            _Values = new List<HValue>();
            _Values.Clear();
            this.PushCount = 0;
        }

        public void Push(HValue value)
        {
            _Values.Add(value);
            int pos = _Values.Count - 1;
            Upper(pos);
            this.PushCount++;

            //this.AllDiffer();
            //this.Validate();
        }

        public HValue Peek()
        {
            if (_Values.Count >= 1)
                return _Values[0];
            else
                return null;
        }

        public HValue Pop()
        {
            if (_Values.Count >= 1)
            {
                HValue ret = _Values[0];
                _Values[0] = _Values[_Values.Count - 1];
                _Values.RemoveAt(_Values.Count - 1);
                Lower(0);
                return ret;
            }
            else
                return null;
        }

        public void Upper(int pos)
        {
            int current = pos;
            int father = (pos - 1) / 2;

            while (true)
            {
                father = (current - 1) / 2;

                if (current != 0 && HValue.Compare(_Values[current], _Values[father]))
                {
                    HValue temp = _Values[current];
                    _Values[current] = _Values[father];
                    _Values[father] = temp;

                    current = father;
                    // this.AllDiffer();
                }
                else
                {
                    break;
                }
            }
        }

        public void Lower(int pos)
        {
            if (_Values.Count == 0)
                return;

            int current = pos;
            int childL = pos * 2 + 1;
            int childR = pos * 2 + 2;

            while (true)
            {
                int choose = current;
                childL = current * 2 + 1;
                childR = current * 2 + 2;
                if (childL < _Values.Count && HValue.Compare(_Values[childL], _Values[choose])) choose = childL;
                if (childR < _Values.Count && HValue.Compare(_Values[childR], _Values[choose])) choose = childR;

                if (choose == current)
                {
                    break;
                }
                else
                {
                    HValue temp = _Values[current];
                    _Values[current] = _Values[choose];
                    _Values[choose] = temp;

                    current = choose;

                    // this.AllDiffer();
                }
            }

            //this.Validate();
        }

        public bool Validate()
        {
            return true;
            bool ret = true;
            for (int i = 0; i < _Values.Count; i++)
            {
                if (i * 2 + 1 < _Values.Count && HValue.Compare(_Values[2 * i + 1], _Values[i]))
                    ret = false;
                if (i * 2 + 2 < _Values.Count && HValue.Compare(_Values[2 * i + 2], _Values[i]))
                    ret = false;
                if (ret == false || i * 2 >= _Values.Count)
                    break;
            }
            return ret;
        }

        public bool AllDiffer()
        {
            for (int i = 0; i < _Values.Count; i++)
                for (int j = i + 1; j < _Values.Count; j++)
                    if (_Values[i].X == _Values[j].X &&
                        _Values[i].Y == _Values[j].Y)
                    {
                        return false;
                        if (_Values[i] == _Values[j])
                        {
                            Debug.WriteLine("Same object.");
                        }
                    }
            return true;
        }
    }
}
